package hot_100;

import java.util.Arrays;

public class 最长递增子序列 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 2, 3};
        int s = lengthOfLIS(nums);
        System.out.println(s);
    }

//    public int lengthOfLIS(int[] nums) {
//        int n = nums.length;
//        int[] dp = new int[n + 1];
//        Arrays.fill(dp, 1);
//        int ans = 1;
//        for (int i = 0; i < n; i++) {
//            for (int j = i - 1; j >= 0; j--) {
//                if (nums[i] > nums[j]) {
//                    dp[i] = Math.max(dp[i], dp[j] + 1);
//                    ans = Math.max(ans, dp[i]);
//                }
//            }
//        }
//        return ans;
//    }

    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int cnt = 0;
        dp[0] = -0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            if (nums[i] > dp[cnt]) {
                dp[++cnt] = nums[i];
            } else {
                int l = 1, r = cnt;
                while (r > l) {
                    int mid = (r + l) >> 1;
                    if (dp[mid] >= nums[i]) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                if (dp[r] > nums[i])
                    dp[r] = nums[i];
            }
        }
        return cnt;
    }
}
